export class MinHeap {
  constructor() {
    this.heap = [];
  }
  // 交换
  swap = (i1, i2) => {
    let temp = this.heap[i1]
    this.heap[i1] = this.heap[i2]
    this.heap[i2] = temp
  }
  // 获取父节点位置
  getParentIndex = (i) => {
    return (i - 1) >> 1
  }
   // 获取左子节点位置
   getLeftIndex = (i) => {
    return 2 * i + 1
  }
   // 获取右子节点位置
   getRightIndex = (i) => {
    return 2 * i + 2
  }
  // 上移
  upShift= (index) => {
    if(index === 0) return
    const parentIndex = this.getParentIndex(index)
    if(this.judgeUpper(parentIndex, index)) {
      this.swap(index, parentIndex)
      this.upShift(parentIndex)
    }
  }

  judgeUpper = (index1, index2) => {
        let [number1, count1] = this.getRealNumberCount(index1);
        let [number2, count2] = this.getRealNumberCount(index2);
        if (number1 === number2) {
            return count1 > count2;
        }
        return number1 > number2;

  }

  getRealNumberCount = (index) => {
      let value = this.getValue(index);
      return value.split(",").map(x=>parseInt(x));
  }

  judgeLower = (index1, index2) => {
      let [number1, count1] = this.getRealNumberCount(index1);
      let [number2, count2] = this.getRealNumberCount(index2);
      if (number1 === number2) {
          return count1 < count2;
      }
      return number1 < number2;
  }
  getValue = (index) => {
      let nowElement = this.heap[index];
      return this.heap[index].getNode();
  }

  // 下移
  downShift= (index) => {
    const leftIndex = this.getLeftIndex(index)
    const rightIndex = this.getRightIndex(index)
    if(leftIndex < this.getLength() && this.judgeLower(leftIndex, index)) {
      this.swap(leftIndex, index)
      this.downShift(leftIndex)
    }
    if(rightIndex < this.getLength() && this.judgeLower(rightIndex, index)) {
      this.swap(rightIndex, index)
      this.downShift(rightIndex)
    }
  }
  // 插入
    insert= (value) => {
    this.heap.push(value)
    this.upShift(this.heap.length - 1)
  }
  // 删除堆顶
    pop= () => {
        let peek = this.peek();
        if (this.heap.length > 1) {
            this.heap[0] = this.heap.pop();
        } else {
            this.heap.pop();
        }
        this.downShift(0)
        return peek;
  }

  // 获取堆顶
    peek = () => this.heap[0];

    getAll = () => {
      return this.heap;
  }

    getLength = () => {
        return this.heap.length;
    }
}